# 这里是快速排序

# 算法思想: 归并排序是一种基于分治法的排序算法，它将数组递归地分成两个子数组，分别排序后再合并
# 时间复杂度为O(n log n)，因为数组每次都被二分，合并的时间复杂度为O(n)
# 空间复杂度为O(n), 因为需要额外的空间来存储临时数组

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    # 找到数组的中间点
    mid = len(nums) // 2
    # 将数组分成两半
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])

    # 递归地对两个子数组进行排序
    merge_sort(left)
    merge_sort(right)

    # 初始化指针
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            nums[k] = left[i]
            i += 1
            k += 1
        else:
            nums[k] = right[j]
            j += 1
        k += 1

    # 检查剩余元素
    while i < len(left):
        nums[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        nums[k] = right[j]
        j += 1
        k += 1

    return nums


def sort_array(nums):
    merge_sort(nums)
    print(nums)



